Quicksort 1 - Partition

The previous challenges covered Insertion Sort, which is a simple and intuitive sorting algorithm with an average case performance of O(n^2). In these next few challenges, we’re covering a divide-and-conquer algorithm called Quicksort (also known as Partition Sort).
在前面的任务中提及的插入排序，是一种很简单直观的排序算法，其平均算法复杂度为O(n^2).在接下来的一些任务中，我们将涉及到一种分治的算法成为快速排序（又称分区排序）。

Step 1: Divide （第一步：分解）

Choose some pivot element, p, and partition your unsorted array,ar , into three smaller arrays:left ,right , and equal, where each element in left<p, each element in right>p, and each element in equal=p.
选择某个基准元素p，然后将你待排序的数组ar分成三个小的数组left，right，equal，所有其中的元素满足：left<p,right>p,equal=p

Challenge (任务)

Given ar and p=ar[0] , partition ar into left,right , and equal using the Divide instructions above. Then print each element in left followed by each element in equal, followed by each element in right on a single line. Your output should be space-separated.

Note: There is no need to sort the elements in-place; you can create two lists and stitch them together at the end.
给你数组ar和p=ar[0],使用上面的分解指令将ar分成left，right，equal。然后依次打印left，equal，right中的元素，用空格隔开。

Input Format（输入格式）

The first line contains n (the size of ar).
The second line contains n space-separated integers describing ar (the unsorted array). The first integer (corresponding to ar[0]) is your pivot element,p.
第一行为n
第二行为n个空格隔开的ar中的整数，p=ar[0]

Constraints（约束条件）

  • 1<=n<=1000
  • -1000<=x<=1000,x in ar
    All elements will be unique.
    Multiple answer can exists for the given test case. Print any one of them.
    所有元素唯一，答案不唯一，可以打印其中任何一个

    Output Format（输出格式）

On a single line, print the partitioned numbers (i.e.: the elements in left, then the elements in equal, and then the elements in right). Each integer should be separated by a single space.
一行，输出分区后的数字

Sample Input（输入样例）

5
4 5 3 7 2

Sample Output（输出样例）

3 2 4 5 7

Explanation（解释）

ar=[4,5,3,7,2]

Pivot: p=ar[0]=4.
left={};equal{4} ;right={}

ar[1]=5>=p, so it’s added to right.
left={};equal{4} ;right={5}

ar[2]=3<=p, so it’s added toleft.
left={3};equal{4} ;right={5}

ar[3]=7>=p, so it’s added to right.
left={3};equal{4} ;right={5,7}

ar[4]=2<=p, so it’s added to left.
left={3,2};equal{4} ;right={5,7}

We then print the elements of left, followed by equal, followed by right, we get: 3 2 4 5 7.

This example is only one correct answer based on the implementation shown, but it is not the only correct answer (e.g.: another valid solution would be 2 3 4 5 7).
这只是其中一个正确的答案（答案还可能是2 3 4 5 7）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void partition(vector <int>  ar) {
    // Enter code for partitioning and printing here. 
    int p=ar[0];
    int i=0; //right bounder of left partition 
    for(int j=1;j<ar.size();j++){ //go through all the elements in ar
        if (ar[j]<p){ //add to left partition
            i++;
            int t=ar[i];
            ar[i]=ar[j];
            ar[j]=t;
        }
    }
    int t=ar[0];ar[0]=ar[i];ar[i]=t;
    for(int i=0;i<ar.size();i++){
        cout<<ar[i]<<" ";
    }
}
int main(void) {
   vector <int>  _ar;
   int _ar_size;
   cin >> _ar_size;
    
     for(int _ar_i=0; _ar_i<_ar_size; _ar_i++) {
        int _ar_tmp;
        cin >> _ar_tmp;
        _ar.push_back(_ar_tmp); 
    }

   partition(_ar);
   
   return 0;
}